#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

//矩阵中的路径，递归
bool helper(char *matrix, int &rows, int &cols, int i, int j, char *str, vector<vector<bool>> &mark)
{
    if (*str == '\0')
    {
        return true;
    }
    if (i < 0 || i >= rows || j < 0 || j >= cols)
    {
        return false;
    }
    if (mark[i][j])
    {
        return false;
    }
    if (matrix[i * cols + j] != *str)
    {
        return false;
    }
    else
    {
        mark[i][j] = true;
        bool ans = helper(matrix, rows, cols, i + 1, j, str + 1, mark) || helper(matrix, rows, cols, i, j + 1, str + 1, mark) || helper(matrix, rows, cols, i - 1, j, str + 1, mark) || helper(matrix, rows, cols, i, j - 1, str + 1, mark);
        mark[i][j] = false;
        return ans;
    }
}

bool hasPath(char *matrix, int rows, int cols, char *str)
{
    for (int i = 0; i < rows; ++i)
    {
        for (int j = 0; j < cols; ++j)
        {
            vector<vector<bool>> mark(rows, vector<bool>(cols, false));
            if (helper(matrix, rows, cols, i, j, str, mark))
            {
                return true;
            }
        }
    }
    return false;
}

void test()
{
    hasPath("ABCESFCSADEE", 3, 4, "ABCCED");
}

int main()
{
    test();
    return 0;
}